class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        
        int n=nums.size();
        const int INF=0x3f3f3f3f;
        vector<vector<int>> dp(n+1,vector<int>(3,-INF));
        dp[0][0]=0;
        for(int i=1;i<=n;++i){
            for(int j=0;j<3;++j){
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
                int newRemain=(j+nums[i-1])%3;
                dp[i][newRemain]=max(dp[i][newRemain],dp[i-1][j]+nums[i-1]);
            }
        }

        return max(dp[n][0],0);
    }
};
